package com.uyong.study.algorithm.search;

/**
 * 二分查找O(logn)
 * 
 * @author gonggy
 * @since 2019-02-13
 */
public class BSearch {

	/**
	 * 简单二分查找，不特殊处理重复值<br> 查找value，并返回value在数组中的下标，没有则返回-1
	 * 
	 * @param data  必须是有序数组
	 * @param value
	 * @return
	 */
	public int simpleSearch(int[] data, int value) {
		int low = 0;
		int high = data.length - 1;
		// 必须low<=high
		while (low <= high) {
			// 防止大小溢出；移位运算更快
			int mid = low + ((high - low) >> 1);
			if (data[mid] == value) {
				return mid;
			} else if (data[mid] > value) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}
		return -1;
	}

	/**
	 * 二分查找第一个值等于给定值的数组下标，没有则返回-1
	 * 
	 * @param data
	 * @param value
	 * @return
	 */
	public int firstEqualSearch(int[] data, int value) {
		int low = 0;
		int high = data.length - 1;
		while (low <= high) {
			int mid = low + ((high - low) >> 1);
			if (data[mid] > value) {
				high = mid - 1;
			} else if (data[mid] < value) {
				low = mid + 1;
			} else {
				// 如果mid是数组的第一个元素，或者mid的前一个元素不等于value，则表示value的第一个数组下标是mid
				if (mid == 0 || data[mid - 1] != value) {
					return mid;
				} else {
					high = mid - 1;
				}
			}
		}
		return -1;
	}

	/**
	 * 二分查找最后一个值等于给定值的 数组下标，没有则返回-1
	 * 
	 * @param data
	 * @param value
	 * @return
	 */
	public int lastEqualSearch(int[] data, int value) {
		int low = 0;
		int high = data.length - 1;
		while (low <= high) {
			int mid = low + ((high - low) >> 1);
			if (data[mid] > value) {
				high = mid - 1;
			} else if (data[mid] < value) {
				low = mid + 1;
			} else {
				if ((mid == data.length - 1) || (data[mid + 1] != value)) {
					return mid;
				} else {
					low = mid + 1;
				}
			}
		}
		return -1;
	}

	/**
	 * 二分查找第一个大于等于给定值的数组下标，没有则返回-1
	 * 
	 * @param data
	 * @param value
	 * @return
	 */
	public int firstGteSearch(int[] data, int value) {
		int low = 0;
		int high = data.length - 1;
		while (low <= high) {
			int mid = low + ((high - low) >> 1);
			if (data[mid] >= value) {
				if (mid == 0 || data[mid - 1] < value) {
					return mid;
				} else {
					high = mid - 1;
				}
			} else {
				low = mid + 1;
			}
		}
		return -1;
	}

	/**
	 * 二分查找最后一个小于等于给定值的数组下标，没有则返回-1
	 * 
	 * @param data
	 * @param value
	 * @return
	 */
	public int lastLteSearch(int[] data, int value) {
		int low = 0;
		int high = data.length - 1;
		while (low <= high) {
			int mid = low + ((high - low) >> 1);
			if (data[mid] <= value) {
				if (mid == data.length - 1 || data[mid + 1] > value) {
					return mid;
				}
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}
		return -1;
	}
}
